
void Sort_(int arr[], int index)
{
    if (index <= 0 || arr[index] < arr[index - 1])
        return;

    std::swap(arr[index], arr[index - 1]);
    Sort_(arr, index - 1);
}

void InsertSort(int arr[], int index)
{
    if (index <= 0)
        return;

    InsertSort(arr, index - 1);
    Sort_(arr, index);
}